package bin_tree.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author yuisama
 * @date 2023/03/24 21:33
 **/
public class Num958_IsCompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isStep1 = true;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (isStep1) {
                // 此时处在阶段1，每个节点都必须有左右两个子树
                // 当碰到第一个度为1(只有左孩子)或度为0，转阶段
                if (node.left != null && node.right != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
                else if (node.left !=null) {
                    // 当前节点只有左孩子
                    queue.offer(node.left);
                    // 转阶段
                    isStep1 = false;
                }else if (node.right != null) {
                    // 当前节点只有右孩子
                    // 找到反例
                    return false;
                }else {
                    // 当前节点是第一个碰到的叶子结点
                    isStep1 = false;
                }
            }else {
                // 在阶段2中每个节点都只可能是叶子结点
                if (node.left != null || node.right != null) {
                    return false;
                }
            }
        }
        return true;
    }
}